import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution131 {
    public List<List<String>> partition(String s) {
        boolean[][] f=new boolean[s.length()][s.length()];
        for (boolean[] booleans : f) {
            Arrays.fill(booleans,true);
        }
        for (int i=s.length()-1;i>=0;i--){
            for (int j=i+1;j<s.length();j++){
                f[i][j]=s.charAt(i)==s.charAt(j)&&f[i+1][j-1];
            }
        }
        List<List<String>> ans=new ArrayList<>();
        List<String> temp=new ArrayList<>();
        dfs(0,temp,ans,f,s);
        return ans;
    }

    private void dfs(int k, List<String> temp, List<List<String>> ans, boolean[][] f, String s) {
        if (k>=s.length()){
            ans.add(new ArrayList<>(temp));
            return;
        }
        for (int i=k;i<s.length();i++){
            if (f[k][i]){
                temp.add(s.substring(k,i+1));
                dfs(i+1,temp,ans,f,s);
                temp.remove(temp.size()-1);
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(new Solution131().partition("aab"));
    }

}
